/*
 * @Author: szx
 * @Date: 2021-11-03 15:53:46
 * @LastEditTime: 2021-11-03 16:34:20
 * @Description:
 * @FilePath: \leetcode\900-999\994\994.cpp
 */
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Solution {
   private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

   public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        queue<pair<int, int>> q;
        int t1 = 0, t2 = 0, t3 = 0;
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    q.emplace(i, j);
                    t1++;
                } else if (grid[i][j] == 1) {
                    t3++;
                }
            }
        }

        if (t1 == 0) {
            if (t3) {
                return -1;
            }
            return 0;
        }
        int res = 0;
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            t1--;
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
                    grid[ni][nj] == 1) {
                    grid[ni][nj] = 2;
                    q.emplace(ni, nj);
                    t2++;
                }
            }
            if (t1 == 0) {
                res++;
                t1 = t2;
                t2 = 0;
            }
        }
        for (int a = 0; a < m; a++) {
            for (int b = 0; b < n; b++) {
                if (grid[a][b] == 1) {
                    return -1;
                }
            }
        }
        return res - 1;
    }
};